/*
 *https://leetcode.cn/problems/sum-of-absolute-differences-in-a-sorted-array/
 *1685. 有序数组中差绝对值之和
 *medium 吴朝泽 2024.11.30
 *前缀和 后缀和 用嵌套会超时
*/

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 0);
        
        // 计算每个元素与左侧元素的差的绝对值之和
        long long leftSum = 0; // 累加左侧元素的和
        for (int i = 0; i < n; ++i) 
        {
            ans[i] += i * (long long)nums[i] - leftSum; // 当前元素与左侧元素差的绝对值和
            leftSum += nums[i]; // 更新左侧元素和
        }
        
        // 计算每个元素与右侧元素的差的绝对值之和
        long long rightSum = 0; // 累加右侧元素的和
        for (int i = n - 1; i >= 0; --i) 
        {
            ans[i] += rightSum - (n - 1 - i) * (long long)nums[i]; // 当前元素与右侧元素差的绝对值和
            rightSum += nums[i]; // 更新右侧元素和
        }

        return ans;
    }
};

/*
sumLeft = i × nums[i] − leftSum   sumLeft：左侧差值之和  leftSum：累加左侧元素的和
sumRight = rightSum − (n − 1 − i) × nums[i]
*/
